package puzzle.projecteuler.p200;

import java.math.BigInteger;


public class Problem162C {

	/**
	 * K位数中，满足条件的数有：15*16^(K-1)
	 * S_i = { 每一位都不是i的所有K位数 }
	 * 问题是要求S0, S1, S_10 (A==10)的并集的补集大小。
	 * 利用容斥原理，容易得到大小是：
	 * S = 15*16^(K-1) - 15^K - 2*14*15^(K-1) + 13*14^(K-1) + 2*14^K - 13^K
	 *   = 15*16^(K-1) - 43*15^(K-1) + 41*14^(K-1) - 13^K
	 * S0 		= 15^K
	 * S1 		= 14*15^(K-1)
	 * S10 		= 14*15^(K-1)
	 * S0^S1	= 14^K 
	 * S0^S10	= 14^K
	 * S1^S10	= 13*14^(K-1)
	 * S0^S1^S10= 13^K
	 * 
	 *    
	 * answer	: 3D58725572C62302
	 * time cost: 0 ms
	 * 
	 * @param args
	 */
	public static void main(String[] args) {

		long start = System.currentTimeMillis();
		BigInteger count = BigInteger.ZERO;
		for (int K = 1; K <= 16; K ++) {
			count = count.add(count(K));
		}
		System.out.println(count.toString(16).toUpperCase());
		System.out.println((System.currentTimeMillis()-start) + " ms");
	}
	
	private static BigInteger count(int K) {
		
		BigInteger S = BigInteger.valueOf(15).multiply(BigInteger.valueOf(16).pow(K-1));
		S = S.subtract(BigInteger.valueOf(43).multiply(BigInteger.valueOf(15).pow(K-1)));
		S = S.add(BigInteger.valueOf(41).multiply(BigInteger.valueOf(14).pow(K-1)));
		S = S.subtract(BigInteger.valueOf(13).pow(K));
		return S;
	}
}
